import heapq
from typing import List


class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])  # 将课程按最晚开始时间排序

        heap = []
        now = 0
        for during, end in courses:
            if now + during <= end:
                now += during
                heapq.heappush(heap, -during)
            else:
                if heap and -heap[0] > during:  # 将之前时间最长的课换成新的课
                    now -= -heapq.heappop(heap)
                    now += during
                    heapq.heappush(heap, -during)
        return len(heap)


if __name__ == "__main__":
    print(Solution().scheduleCourse([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]))  # 3

    # 测试用例2/97
    print(Solution().scheduleCourse([[3, 2], [4, 3]]))  # 0

    # 测试用例11/97
    print(Solution().scheduleCourse([[1, 2], [2, 3]]))  # 2
